SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Multidimensional parity-check code</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Multidimensional parity-check code</span></span>

</h1>

</header>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><p>A <b>multidimensional parity-check code (MDPC)</b> is a type of <a href="Error-correcting_code" class="mw-redirect" title="Error-correcting code">error-correcting code</a> that generalizes two-dimensional <a href="Parity_check" class="mw-redirect" title="Parity check">parity checks</a> to higher dimensions. It was developed as an extension of simple parity check methods used in <a href="Magnetic_tape" title="Magnetic tape">magnetic recording systems</a> and <a href="Radiation_hardening" title="Radiation hardening">radiation-hardened</a> <a href="Memory_architecture" title="Memory architecture">memory designs</a>.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Overview">Overview</h2></div>

<p>In an MDPC code, information bits are organized into an <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math></span><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"></span>-dimensional structure, where each <a href="Bit" title="Bit">bit</a> is protected by <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math></span><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"></span> <a href="Parity_bit" title="Parity bit">parity bits</a>. Each parity bit is calculated along a different dimensional axis. The code can be characterized by its <i>dimension vector</i> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r=[r_{1},r_{2},\cdots ,r_{n}]}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r=[r_{1},r_{2},\cdots ,r_{n}]}</annotation>

</semantics>

</math></span><img src="./f20d44ff0580ebf7c1beedcc0d8c5693e72cf9f3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.126ex; height:2.843ex;" alt="{\displaystyle r=[r_{1},r_{2},\cdots ,r_{n}]}" loading="lazy"></span>, where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{i}}</annotation>

</semantics>

</math></span><img src="./a0b6d651eaf432dbf1f106021c8bb499ae83fd1f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.848ex; height:2.009ex;" alt="{\displaystyle r_{i}}" loading="lazy"></span> defines the size of the block or multi-block in the <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math></span><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"></span>th dimension. The code length <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math></span><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"></span> can be expressed as

</p>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c=\prod _{n=1}^{N}r_{n}}</annotation>

</semantics>

</math></span><img src="./82f8c359cdf2966fd8a122f67f72d29459f9b48e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:9.846ex; height:7.343ex;" alt="{\displaystyle c=\prod _{n=1}^{N}r_{n}}" loading="lazy"></span></dd></dl>

<p>while the number of information bits <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math></span><img src="./e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"></span> is given by

</p>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d=\prod _{n=1}^{N}(r_{n}-1)}</annotation>

</semantics>

</math></span><img src="./320ae9bd7a27e0c51aa13986f5bdb2582d8cd838.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:15.48ex; height:7.343ex;" alt="{\displaystyle d=\prod _{n=1}^{N}(r_{n}-1)}" loading="lazy"></span>.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Reduced_generator_matrices">Reduced generator matrices</h3></div>

<p><i>Reduced generator matrices</i> eliminate redundant <a href="Parity_bits" class="mw-redirect" title="Parity bits">parity bits</a> while maintaining error correction capabilities. This modification increases the code rate without significantly degrading performance. The code rate <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R}</annotation>

</semantics>

</math></span><img src="./4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy"></span> for a reduced MDPC is given by

</p>

<mfrac>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R={\frac {d}{c}}={\frac {\prod _{n=1}^{N}(r_{n}-1)}{\prod _{n=1}^{N}r_{n}}}}</annotation>

</semantics>

</math></span><img src="./3f37a70e24d1ddf1ef371b97598651c451e46ba3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:24.441ex; height:7.509ex;" alt="{\displaystyle R={\frac {d}{c}}={\frac {\prod _{n=1}^{N}(r_{n}-1)}{\prod _{n=1}^{N}r_{n}}}}" loading="lazy"></span>.</dd></dl>

<p>The reduced generator matrix can be created using systematic construction methods, resulting in more efficient encoding processes compared to traditional parity check codes.

</p><p>The following <a href="Pseudocode" title="Pseudocode">pseudocode</a> shows how to generate a reduced generator matrix:<sup id="cite_ref-Dudacek-2016_3-0" class="reference"><a href="#cite_note-Dudacek-2016-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p>

<pre><b>function</b> function_name <b>is</b>

<i>// Initialize G with identity matrix augmented with ones column</i>

G ← [I_{r<sub>1</sub>-1} | 1_{(r<sub>1</sub>-1)×1}]

<i>// Update G with Kronecker product</i>

G ← I_{r_n-1} ⊗ G

<i>// Calculate product of previous dimensions</i>

x ← Π<sub>i=1</sub><sup>n-1</sup>(r<sub>i</sub> - 1)

<i>// Create temporary matrix with ones column and identity</i>

G_tmp ← 1_{(r_n-1)×1} ⊗ I_x

<i>// Augment G with temporary matrix</i>

G ← [G | G_tmp]

<b>return</b> G

<b>end function</b>

</pre>

<div class="mw-heading mw-heading3"><h3 id="Decoding_algorithms">Decoding algorithms</h3></div>

<p>Decoding in MDPC systems typically employs an <a href="Iterative_algorithm" class="mw-redirect" title="Iterative algorithm">iterative algorithm</a> based on <i>Failed Dimension Markers (FDM)</i>, which indicate the number of parity check failures associated with each information bit. The FDM-based decoding process works by identifying bits with the highest probability of error and iteratively attempting corrections until either all errors are resolved or a maximum iteration limit is reached.<sup id="cite_ref-Dudacek-2016_3-1" class="reference"><a href="#cite_note-Dudacek-2016-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

<p>MDPC codes have applications in scenarios where short block lengths are required, such as <a href="Real-time_communication" title="Real-time communication">real-time communications</a> systems and <a href="Memory_protection" title="Memory protection">memory protection</a> schemes. They offer several advantages over other <a href="Error-correcting_codes" class="mw-redirect" title="Error-correcting codes">error-correcting codes</a>, including positive code gain at low <a href="Signal-to-noise_ratio" title="Signal-to-noise ratio">signal-to-noise ratios</a> and simpler implementation complexity compared to LDPC codes. The level of error protection can be adjusted by modifying the number of dimensions or the size of each dimension, allowing for flexibility in design trade-offs between code rate and error correction capability.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFQ._L._Rao,_C._He2009" class="citation conference cs1">Q. L. Rao, C. He (2009). <i>A new 2-D parity checking architecture for radiation-hardened by design SRAM</i>. <i>Asia Pacific Conference on Postgraduate Research in Microelectronics & Electronics</i>. pp. <span class="nowrap">360–</span>363.</cite></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite id="CITEREFJ._M._Shea,_T._F._Wong2003" class="citation journal cs1">J. M. Shea, T. F. Wong (2003). "Multidimensional Codes". <i>Encyclopedia of Telecommunications</i>. Wiley.</cite></span>

</li>

<li id="cite_note-Dudacek-2016-3"><span class="mw-cite-backlink">^ <a href="#cite_ref-Dudacek-2016_3-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Dudacek-2016_3-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFLudek_Dudácek,_Ivo_Vertat2016" class="citation conference cs1">Ludek Dudácek, Ivo Vertat (2016). <i>Multidimensional Parity Check codes with short block lengths</i>. <i>24th Telecommunications Forum TELFOR</i>. pp. <span class="nowrap">1–</span>4.</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFA._Vadinala,_G._K._Kumar2013" class="citation conference cs1">A. Vadinala, G. K. Kumar (2013). <i>Multi Dimensional Parity Based Hamming Codes For Correcting The SRAM Memory Faults Under High EMI Conditions</i>. <i>IACEECE International Conference</i>. pp. <span class="nowrap">46–</span>49.</cite></span>

</li>

</ol></div></div>

<ul><li><a href="Error_detection_and_correction" title="Error detection and correction">Error detection and correction</a></li>

<li><a href="Forward_error_correction" class="mw-redirect" title="Forward error correction">Forward error correction</a></li>

<li><a href="Low-density_parity-check_code" title="Low-density parity-check code">Low-density parity-check code</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-02-06" href="https://en.wikipedia.org/wiki/?title=Multidimensional_parity-check_code&oldid=1274264320">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>